package org.geekbang.time.mathbasicthought.lesson5_recursive;

import java.util.ArrayList;

public class RewardMoney {
    // 4种面额
    public static int[] rewards = {1, 2, 5, 10};

    public static void main(String[] args) {
        // get(10, new ArrayList<>());
        //get2(0, new ArrayList<>());
        thinkQ(8, new ArrayList<>());
        //recursion(8, new ArrayList<>());
    }

    public static void get(int totalMoney, ArrayList<Integer> result) {
        // 当totalMoney等于0时，证明它是满足条件的解，结束嵌套调用，输出解
        if (totalMoney == 0) {
            System.out.println(result);
            return;
        }
        // 当totalMoney小于0时，证明它不是满足条件的解
        else if (totalMoney < 0) {
            return;
        } else {
            for (int i = 0; i < rewards.length; i++) {
                // 由于有4种情况，需要clone当前的解并传入被调用的参数
                ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
                // 记录当前的选择，解决一点问题
                newResult.add(rewards[i]);
                // 剩下的问题，留给嵌套调用
                get(totalMoney - rewards[i], newResult);
            }
        }
    }

    public static void get2(int currentMoney, ArrayList<Integer> result) {
        if (currentMoney == 10) {
            System.out.println(result);
            return;
        }
        if (currentMoney > 10)
            return;

        for (int i = 0; i < rewards.length; i++) {
            // 由于有4种情况，需要clone当前的解并传入被调用的参数
            ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
            newResult.add(rewards[i]);
            get2(currentMoney + rewards[i], newResult);
        }
    }

    public static void thinkQ(int targetNum, ArrayList<Integer> result) {
        if (targetNum == 1) {
            if (!result.contains(1)) result.add(1);
            System.out.println(result);
            return;
        }

        for (int i = targetNum; i >= 1; i--) {
            if ((i == 1) && result.contains(1)) continue;
            ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
            newResult.add(i);
            if (targetNum % i != 0) {
                continue;
            }
            thinkQ(targetNum / i, newResult);
        }
    }

    public static void recursion(long total, ArrayList<Long> result) {

        if (total == 1) {
            if (!result.contains(1L)) result.add(1L);
            System.out.println(result);
            return;
        } else {
            for (long i = 1; i <= total; i++) {
                if ((i == 1) && result.contains(1L)) continue;
                ArrayList<Long> newList = (ArrayList<Long>) (result.clone());
                newList.add(Long.valueOf(i));
                if (total % i != 0) {
                    continue;
                }
                recursion(total / i, newList);
            }
        }
    }


}
